#include <stdio.h>
#include <conio.h>
#define NULL 0
struct rec
{
  int data;
  struct rec * lchild;
  struct rec *rchild;
};

typedef struct rec tree;
tree *par,*ptr,*root,*loc;
char treech='y',rch,lch,che;
int flag=0;

void preorder(tree *node)
 {
   if(node!=NULL)
   {
      printf("%d\t",node->data);
      preorder(node->lchild);
      preorder(node->rchild);
   }
 }


void inorder(tree *node)
 {
   if(node!=NULL)
   {
      inorder(node->lchild);
      printf("%d\t",node->data);
      inorder(node->rchild);
   }
 }

void postorder(tree *node)
 {
   if(node!=NULL)
   {
      postorder(node->lchild);
      postorder(node->rchild);
      printf("%d\t",node->data);
   }
 }

void main()
 {
  char choice,ch[2];
   do
   {
    clrscr();
    printf("--- BINARY SEARCH TREE ---\n");
    printf("<C> . . .Create\n<I> . . .Insert\n<D> . . .Delete\n");
    printf("<P> . . .Preorder\n<Q> . . .Inorder\n<R> . . .Postorder\n");
    printf("<X> . . .Exit\n");
    printf("\nChoice: ");
    che=toupper(getche());
    switch(che)
    {
     case 'A':
	    clrscr();
	    printf("\n--- Create ---\n");
	    root=(tree *) malloc (sizeof(tree));
	    printf("Root: ");
	    scanf("%d",&root->data);
	    root->rchild=NULL;
	    root->lchild=NULL;
	    strcpy(ch,"y");
	    while((strcmp(ch,"y")==0))
	    {
	      printf("More?(y/n):- ");
	      scanf("%s",ch);
	      if(strcmp(ch,"y")==0)insert();
	    }
	    break;
     case 'I':
	    clrscr();
	    insert();
	    break;
     case 'D':
	    clrscr();
	    delete();
	    break;
     case 'P':
	    clrscr();
	    printf("\nPreorder traversal\n");
	    preorder(root);
	    printf("\n");
	    printf("Press any key to continue..\n\n");
	    getch();
	    break;
     case 'Q':
	    clrscr();
	    printf("Inorder traversal\n");
	    inorder(root);
	    printf("\n");
	    printf("Press any key to continue..\n\n");
	    getch();
	    break;
     case 'R':
	    clrscr();
	    printf("Postorder traversal\n");
	    postorder(root);
	    printf("\n");
	    printf("Press any key to continue..\n");
	    getch();
     }
 }while(che!='X');
}





 findloc(tree *item)
 {
    par=(tree *) malloc (sizeof(tree));
    ptr=(tree *) malloc (sizeof(tree));

  if(item->data==root->data)
  {
      par=NULL;
      return;
  }

  if(item->data < root->data)
   {
       par=root;
       ptr=root->lchild;
   }
   else
   {
       par=root;
       ptr=root->rchild;
   }

   while(ptr!=NULL)
   {
      if(item->data == ptr->data)break;

      if(item->data > ptr->data)
      {
	 par=ptr;
	 ptr=ptr->rchild;
      }

      if(item->data < ptr->data)
      {
	par=ptr;
	ptr=ptr->lchild;
      }
   }
}

insert()
 {
  tree *item;
  printf("\nValue:  ");
  item=(tree *) malloc (sizeof(tree));
  scanf("%d",&item->data);

  findloc(item);
  if(par==NULL)
  {
       item->rchild=root->rchild;
       root->rchild=item;
       item->lchild=NULL;
       return;
  }
  if(ptr==NULL)
  {
     if(item->data < par->data)
     {
	item->lchild=NULL;
	item->rchild=NULL;
	par->lchild=item;
	return;
     }
     else if(item->data > par->data)
     {
	item->lchild=NULL;
	item->rchild=NULL;
	par->rchild=item;
	return;
     }
  }
  else
  {
    if(item->data < par->data)
    {
      item->lchild=par->lchild;
      item->rchild=NULL;
      par->lchild=item;
      return;
    }
    else if(item->data > par->data)
    {
      item->rchild=par->rchild;
      item->lchild=NULL;
      par->rchild=item;
    }
  }
}


delloc(tree *item)
{
    par=(tree *) malloc (sizeof(tree));
    ptr=(tree *) malloc (sizeof(tree));

  if(item->data==root->data)
  {
      loc=root;
      par=NULL;
      return;
  }

  if(item->data < root->data)
   {
       par=root;
       ptr=root->lchild;
   }
   else
   {
       par=root;
       ptr=root->rchild;
   }

   while(ptr!=NULL)
   {
      if(item->data == ptr->data)
      {
	 loc=ptr;
	 return;
      }
      if(item->data < ptr->data)
      {
	 par=ptr;
	 ptr=ptr->lchild;
      }

      if(item->data < ptr->data)
      {
	  par=ptr;
	  ptr=ptr->rchild;
      }
   }
   if(ptr==NULL)
   {
     loc=NULL;
     return;
   }
}


delete()
{
  tree *item,*lo,*pa;
    item=(tree*) malloc (sizeof(tree));
    par=(tree*) malloc (sizeof(tree));
    loc=(tree*) malloc (sizeof(tree));
    lo=(tree*) malloc (sizeof(tree));
    pa=(tree*) malloc (sizeof(tree));

    printf("\n\nEnter the element to be deleted:- ");
    scanf("%d",&item->data);
    loc=(tree *) malloc (sizeof(tree));

    delloc(item);
    if(par==NULL)
    {
      if(root->rchild!=NULL)
      {
	 root->rchild->lchild=root->lchild;
	 root=root->rchild;
      }
      else
      {
	 if(root->lchild!=NULL)root=root->lchild;
      }
      return;
    }

    if(loc==NULL)
    {
       printf("No such elment is present in the tree.\n");
       printf("\nPress enter key to continue...");
       getch();;
       return;
    }
    lo=loc;
    pa=par;

    if(loc->rchild!=NULL && loc->lchild!=NULL)
	deleteB(lo,pa);
    else
	deleteA(lo,pa);
    return;
}

deleteA(tree *lo,tree *pa)
{
  tree *child;
  child=(tree*)malloc(sizeof(tree));
  if(lo->lchild==NULL && lo->rchild==NULL)
  {
   if(lo->data > pa->data )
     pa->rchild=NULL;
   else
     pa->lchild=NULL;
     return;
   }

   if(lo->lchild!=NULL)
    child=lo->lchild;
   else
    child=lo->rchild;

   if(lo==pa->lchild)
     par->lchild=child;
   else
     par->rchild=child;

   return;
}

deleteB(tree *lo,tree *pa)
{
  tree *pt,*save,*succ;
  pt=(tree *) malloc (sizeof(tree));
  save=(tree *) malloc (sizeof(tree));
  succ=(tree *) malloc (sizeof(tree));

  save=lo;
  pt=lo->rchild;

  while(pt->lchild != NULL)
  {
      save=pt;
      pt=pt->lchild;
  }
  succ=pt;

  deleteA(succ,save);

  if(lo == pa->rchild )
      pa->rchild=succ;
  else
      pa->lchild=succ;

  succ->lchild=lo->lchild;
  succ->rchild=lo->rchild;
  return;
}